package cn.antblog.ruankao.tanxinsuanfa;

import java.util.Arrays;

/**
 * 贪心算法装箱问题
 */
public class BinPacking {  
    public static int minBins(int[] weights, int binCapacity) {  
        // 对重量进行排序，从而使得我们可以优先选择重量最小的物品  
        Arrays.sort(weights);  
        int bins = 0;  
        int currentBinWeight = 0;  
        for (int i = 0; i < weights.length; i++) {  
            if (currentBinWeight + weights[i] <= binCapacity) {  
                // 如果当前箱子可以装下这个物品  
                currentBinWeight += weights[i];  
            } else {  
                // 否则，我们需要一个新的箱子  
                bins++;  
                currentBinWeight = weights[i];  
            }  
        }
        // 装箱问题中的“不要忘了最后一个箱子”的意思是在遍历完所有物品后，要确保算上最后一个已经放入物品的箱子。因为在遍历过程中，每当一个物品无法放入当前箱子时，就会新开一个箱子，并将该物品放入新箱子。这样，在遍历结束后，最后一个已经放入物品的箱子可能没有被计入结果中。因此，需要特别注意确保将最后一个箱子计入结果，才能得到正确的装箱数量。
        // 不要忘了最后一个箱子  
        bins++;  
        return bins;  
    }  
      
    public static void main(String[] args) {  
        int[] weights = {10, 20, 30, 40, 50};  
        int binCapacity = 60;  
        System.out.println("Minimum number of bins required: " + minBins(weights, binCapacity));  
    }  
}